package linear_list.leetcode.easy;

/**
 * @Author Stark
 * @Description: 反转链表
 * 题目链接：https://leetcode-cn.com/problems/reverse-linked-list
 * @Date 2022/4/1 22:58
 **/
public class Num206_ReverseList {
    int choice = 1;
    public ListNode reverseList(ListNode head) {
        if(choice == 1) {
            //方法一：遍历链表的过程中改变指向，用一个新的头节点引用表示逆置后的链表头节点
            //注意:注意保存下一个结点,否则改变了当前结点的指向后,原链表就就不到了
            if (head == null || head.next == null)
                return head;
            ListNode newHead = null, cur = head;
            while (cur != null) {
                ListNode tmp = cur.next;
                cur.next = newHead;
                newHead = cur;
                cur = tmp;
            }
            return newHead;
        }else if(choice == 2){
            //方法二：快慢指针，原地改变指向
            //注意头结点要指向空，否则会形成环
            if(head == null || head.next == null){
                return head;
            }
            ListNode fast = head.next,slow = head;
            //头结点指向空
            head.next = null;
            while(fast != null){
                ListNode next = fast.next;
                fast.next = slow;
                slow = fast;
                fast = next;
            }
            return slow;
        }else if(choice == 3){
            //方法三：递归法
            //将需要逆置的两个结点保存起来，当走到末尾就返回该结点，并用一个引用将其保存
            //递归完毕返回栈桢的时候将两个结点连接起来,并将尾节点置空,最后返回头结点.
            if(head == null || head.next == null){
                return head;
            }
            ListNode prev = head,cur = head.next;
            ListNode newHead = reverseList(cur);
            cur.next = prev;
            prev.next = null;
            return newHead;
        }
        return head;
    }
}
